class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        std::vector<int> dp(n + 1, 0);
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i < n + 1; i++)
        {
            dp[i] = std::max(dp[i-1], dp[i-2] + nums[i-1]);
        }
        return dp[n];
    }
};

'''
dp[i] = max(dp[i - 1], dp[i-2] + nums[i-1]) 
表示第i家时偷到的最多的钱。
dp[i - 1]表示i-1家要偷，
dp[i-2]表示i-1家不偷，这样就是i-2家偷到的最多的钱dp[i-2]和第i家偷到钱的总和，两者取最大值迭代。
'''